package com.demo.quickSort;

public class QuickSort {
	
	public void quickSort(int[] arr, int low, int high) {
		int temp;
		int h, l, key;
		h = high;
		l = low;
		key = arr[low];
		while (l < h) {
			while (l < h && arr[h] >= key) h--; 
			if (l < h) {
				temp = arr[h];
				arr[h] = arr[l];
				arr[l] = temp;
				l++;
			} 
			while(l < h && arr[l] <= key) l++;
			if (l < h) {
				temp = arr[l];
				arr[l] = arr[h];
				arr[h] = temp;
				h++;
			}
		}
		showArray(arr);
		if (l > low) {
			quickSort(arr, low, l - 1);
		}
		if (high > l) {
			quickSort(arr, l + 1, high);
			
		}
	}

	public void showArray(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			System.out.print(" " + i + " ");
		}
		System.out.println();
		for(int j = 0; j < arr.length; j++) {
			System.out.print(" " + arr[j] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		// TOD Auto-generated metxds
		QuickSort quickSortTest = new QuickSort();
		int[] inputArr = {2, 3, 1, 41, 25, 21, 6};
		int[] outputArr;
		quickSortTest.quickSort(inputArr, 0, inputArr.length - 1);
	}

}
